#include <bits/stdc++.h>
using namespace std;
class Node {
public:
	int val;
	Node* left;
	Node* right;
	Node* next;
	
	Node() : val(0), left(NULL), right(NULL), next(NULL) {}
	
	Node(int _val) : val(_val), left(NULL), right(NULL), next(NULL) {}
	
	Node(int _val, Node* _left, Node* _right, Node* _next)
	: val(_val), left(_left), right(_right), next(_next) {}
};
class Test{
public:
	Node* connect(Node* root) {
		queue<Node*> que;
		if(root){
			que.push(root);
		}
		while(!que.empty()){
			int size = que.size();
			while(size--){
				Node* cur = que.front();que.pop();
				if(size){
					cur->next = que.front();
				}else{
					cur->next = NULL;
				}
				if(cur->left) que.push(cur->left);
				if(cur->right) que.push(cur->right);
			}
		}
		return root;
	}
};


int main(){
	
	return 0;
}
